package leetcode.editor.cn;

//给定一个二叉树，判断它是否是高度平衡的二叉树。 
//
// 本题中，一棵高度平衡二叉树定义为： 
//
// 
// 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 
// 
//
// 示例 1: 
//
// 给定二叉树 [3,9,20,null,null,15,7] 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7 
//
// 返回 true 。 
// 
//示例 2: 
//
// 给定二叉树 [1,2,2,3,3,null,null,4,4] 
//
//        1
//      / \
//     2   2
//    / \
//   3   3
//  / \
// 4   4
// 
//
// 返回 false 。 
//
// 
// Related Topics 树 深度优先搜索

import lombok.Data;

public class BalancedBinaryTree{
    public static void main(String[] args) {
        Solution solution = new BalancedBinaryTree().new Solution();
        
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    /**
     * 模版一共三步，就是递归的三部曲：
     * 找终止条件：什么时候递归到头了？此题自然是root为空的时候，空树当然是平衡的。
     * 思考返回值，每一级递归应该向上返回什么信息？
     * 单步操作应该怎么写？因为递归就是大量的调用自身的重复操作，因此从宏观上考虑，只用想想单步怎么写就行了，左树和右树应该看成一个整体，
     * 即此时树一共三个节点：root，root.left，root.right。
     */

    class ReturnNode{
        private boolean isBalanced;
        private int height;
        ReturnNode(boolean isBalanced, int height){
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public boolean isBalanced(TreeNode root) {
//       return isBst(root).isBalanced;
       return isBstt(root) != -1;
    }

    // 单次执行过程: 是否终止?->没终止的话，判断是否满足不平衡的三个条件->返回值
    private ReturnNode isBst(TreeNode node){
        //终止条件 node == null
        if(node == null) return new ReturnNode(true,0);
        //
        ReturnNode left = isBst(node.left);
        ReturnNode right = isBst(node.right);
        if(!left.isBalanced || !right.isBalanced){
            return new ReturnNode(false,0);
        }
        if( Math.abs(left.height - right.height) > 1 ) {
            return new ReturnNode(false, 0);
        }
        return new ReturnNode(true,Math.max(left.height,right.height)+1);
    }

    /**
     * 简易版
     * 1. 返回条件: node == null
     * 2. 返回内容: 平衡返回当前左右子树的最大高度，不平衡则返回-1
     * 3. 单次执行过程: 是否终止?->没终止的话，判断是否满足不平衡的三个条件->返回值
     */
    private int isBstt(TreeNode node){
        if(node == null) return 0;
        int left = isBstt(node.left);
        int right = isBstt(node.right);
        if( left == -1 || right == -1 || Math.abs(left - right) > 1){
            return -1;
        }
        return  Math.max(left,right) + 1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}